package demo.hw;

/**
 * 请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
 * 本题含有多组样例输入。
 * 输入描述：
 * 每组样例输入两个正整数n和m，用空格隔开。(1≤n,m≤8)
 * 输出描述：
 * 每组样例输出一行结果
 *
 * 示例1
 * 输入：
 * 2 2
 * 1 2
 * 复制
 * 输出：
 * 6
 * 3
 *
 * @author taqo
 * @date 2021/5/28
 */
public class _走方格的方案数 {
    public static void main(String[] args) {
        int n = 2;// 行
        int m = 2;// 列
        // 1行2列棋盘==2行3列网格
        total(n + 1, m + 1);
    }

    private static void total(int n, int m) {
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < m; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        System.out.println(dp[n - 1][m - 1]);
    }
}
